固定区间 $[l, r]$, 不妨设就是 $[1, n]$, 我们来看有解的充要条件.

先假设有解, 思考怎么找出解. 试想对于一个 $x$, 我们找出所有含有 $x$ 的 $A_i$. 那么 $p(x)$ 必然在所有对应的 $B_i$ 之内.

1. 假如这些 $B_i$ 的交集没有元素, 那么必然无解;
2. 假如这些 $B_i$ 的交集是 $\{ x' \}$, 那么必然有 $p(x) = x'$.
3. 假如这些 $B_i$ 的交集是 $\{ x', y' \}$, 那么 $A_i$ 的交集大小也得是 $2$, 设为 $\{ x, y \}$.
4. 假如这些 $B_i$ 的交集是 $\{ x', y', z' \}$, 那么 $A_i$ 的交集大小也得是 $3$, 设为 $\{ x, y, z \}$.

如果我们从出现次数最多的 $x$ 开始, 那么在情况 3 中, $x$ 和 $y$ 的出现位置完全相同, 因此可以随意地令 $p(x)=x', p(y)=y'$, 或者 $p(x)=y',p(y)=x'$.

因此我们得到一个条件: 任取一些 $i$, 对应的 $A_i$ 的交集大小等于对应的 $B_i$ 的交集大小. 写的形式一点就是 $$ \forall k, \forall i_1, i_2, \dots, i_k, \bigl| A_{i_1} \cap A_{i_2} \cap \dots \cap A_{i_k} \bigr| = \bigl| B_{i_1} \cap B_{i_2} \cap \dots \cap B_{i_k} \bigr|. $$

事实上这个条件是充要的. 假设这个条件成立, 我们可以按出现次数从大到小考虑所有 $x$ 并分配 $p(x)$; 分配完之后把所有 $A_i$ 中的 $x$ 删除, 所有 $B_i$ 中的 $p(x)$ 删除, 剩下的集合序列仍然满足这个条件因此可以重复地分配直到全为空.

考虑怎么维护这个条件. 我们注意到这个条件进一步等价于六个条件:

1. 如果一些 $A_i$ 的交集大小大于等于 $1$, 则对应的 $B_i$ 的交集大小也大于等于 $1$;
2. 如果一些 $A_i$ 的交集大小大于等于 $2$, 则对应的 $B_i$ 的交集大小也大于等于 $2$;
3. 如果一些 $A_i$ 的交集大小大于等于 $3$, 则对应的 $B_i$ 的交集大小也大于等于 $3$.

以及 $A, B$ 互换后的三个条件. 而这三个条件又等价于

1. 对任意的 $x$, 存在 $x'$, 使得 $x \in A_i \implies x' \in B_i$. (考虑包含 $x$ 的所有 $A_i$ 的交集, 下面类似)
2. 对任意两个不同的 $x, y$, 存在不同的 $x', y'$, 使得 $x, y \in A_i \implies x', y' \in B_i$.
3. 对任意三个不同的 $x, y, z$, 存在 $x', y', z'$, 使得 $x, y, z \in A_i \implies x', y', z' \in B_i$.

因此我们双指针往前跑, 同时对每个 $x$ 维护 $x'$ 的候选, 对每组 $(x, y)$ 维护 $(x', y')$ 的候选, 对每组 $(x, y, z)$ 维护 $(x', y', z')$ 的候选即可. (注意到有用的 $(x, y)$ 组只有 $3n$ 种)

找到所有有用的 $(x, y)$ 组并给他们标号可以用桶排做线性.

然后把 $A$ 和 $B$ 反过来也维护起来, 就可以了.

反正这个维护候选的结构很容易做到线性, 就不赘述了. 总复杂度 $O(n)$.